# Merkle-Damgård 구조

Merkle-Damgård 구조는 임의의 길이를 가진 입력 메시지를 고정된 길이의 해시 값으로 변환하기 위해 설계된 해시 함수 설계 구조입니다. 이 구조는 작은 입력 크기를 처리하는 압축 함수를 반복적으로 사용하여, 메시지의 길이에 상관없이 일관된 크기의 출력값을 생성하는 것을 목적으로 합니다.

## 핵심 메커니즘

### 압축 함수 (Compression Function)
Merkle-Damgård 구조의 핵심은 압축 함수입니다. 이 함수는 고정된 크기의 이전 상태값(Chaining Value)과 메시지의 한 블록을 입력으로 받아, 다시 고정된 크기의 새로운 상태값을 출력합니다. 이 과정이 메시지의 모든 블록에 대해 반복되며 최종 해시값이 결정됩니다.

### 패딩 (Padding)
입력 메시지는 압축 함수가 처리할 수 있는 고정된 블록 단위로 나누어져야 합니다. 이를 위해 메시지 끝에 특정 비트를 추가하여 길이를 맞추는 패딩 과정이 필요합니다. 특히, 'Merkle-Damgård strengthening' 기법을 통해 원본 메시지의 전체 길이를 마지막 블록에 포함시킵니다. 이는 서로 다른 메시지가 패딩 후 동일한 결과가 되어 충돌이 발생하는 것을 방지하기 위해 필수적입니다.

### 초기화 벡터 (IV, Initialization Vector)
첫 번째 메시지 블록을 처리할 때, 이전 상태값이 존재하지 않으므로 미리 정의된 고정된 값인 초기화 벡터(IV)를 사용합니다. IV는 해시 함수의 표준 규격에 정의되어 있으며, 모든 사용자가 동일한 IV를 사용해야 동일한 입력에 대해 동일한 해시값을 얻을 수 있습니다.

## 처리 과정

메시지가 해시값으로 변환되는 단계는 다음과 같습니다.

1. **패딩 및 길이 추가**: 입력 메시지에 패딩을 적용하고 원본 길이를 추가하여 고정 크기의 블록($M_1, M_2, \dots, M_n$)으로 나눕니다.
2. **초기화**: 압축 함수의 첫 번째 입력 상태값으로 IV를 설정합니다.
3. **반복 압축**:
   - $H_1 = \text{Compression}(IV, M_1)$
   - $H_2 = \text{Compression}(H_1, M_2)$
   - ...
   - $H_n = \text{Compression}(H_{n-1}, M_n)$
4. **최종 출력**: 마지막 단계의 출력값 $H_n$을 최종 해시값으로 출력합니다. (필요에 따라 최종 결과에 추가 함수를 적용하기도 합니다.)

## 보안성 및 한계점

### 충돌 저항성
Merkle-Damgård 구조의 중요한 이론적 특징은, 사용된 압축 함수가 충돌 저항성(Collision Resistance)을 가진다면, 이를 통해 구축된 전체 해시 함수 역시 충돌 저항성을 가진다는 점이 증명되었다는 것입니다.

### 취약점 및 대안
이 구조는 **길이 확장 공격(Length Extension Attack)**에 취약하다는 치명적인 단점이 있습니다. 공격자가 해시값 $H(M)$과 메시지 $M$의 길이를 알고 있다면, $M$의 내용을 몰라도 $M$ 뒤에 임의의 데이터를 추가한 $H(M \parallel \text{extra})$ 값을 계산할 수 있습니다.
- **해결 방안**: 이를 방지하기 위해 HMAC(Hash-based Message Authentication Code) 구조를 사용하거나, SHA-3에서 채택한 스펀지(Sponge) 구조와 같은 새로운 설계 방식을 도입합니다.

## 대표적인 사례

Merkle-Damgård 구조를 채택하여 설계된 대표적인 해시 함수는 다음과 같습니다.

- MD5
- SHA-1
- SHA-2 (SHA-256, SHA-512 등)